Practice Problems (Week 9)
These practice problems (unlike the exercises) are not assessed. Use them to test your understanding, to challenge yourself, or whatever floats your boat.
1 Poor man's DataKinds
The lecture illustrates the use of the DataKinds language extension
to constrain the possible instantiations of phantom type variables.
This made it impossible to write nonsense like Sq [Bool]
where
a unit of measure was expected.
Another language mechanism that can restrict type instantiation
is type classes. Here's how you might try to achieve the same
effect using type classes.
The idea is that Unit
is
the set of all types that represent units of measure.
This type class has no methods because it's only
used for marking.
data Km data Mile data Sq a class Unit a instance Unit Km instance Unit Mile instance Unit a => Unit(Sq a) data Distance a = Distance Double deriving(Eq,Show) km5 :: Distance Km km5 = Distance 5 mile5 :: Distance Mile mile5 = Distance 5 times :: Unit a => Distance a -> Distance a -> Distance(Sq a) times (Distance x) (Distance y) = Distance(x*y) plus :: Unit a => Distance a -> Distance a -> Distance a plus (Distance x) (Distance y) = Distance(x+y)
How does this approach compare with the DataKinds approach? Which one does a better job of making illegal states unrepresentable? If there are any shortcomings, are there any strategies to overcome or mitigate them that you can think of?
2 Parser combinators
Use the parser combinator library from the Assignment 2 template to write a
parser for Boolean algebra expressions Exp
,
that can parse boolean expressions involving ||
(or), &&
(and), T
(true),
F
(false), negation (!
), and variable names (lower-case strings).
To simplify matters, write a parser that assumes the input is in the following highly restrictive format:
- No whitespace anywhere
- Conjunction and disjunction operators always have parentheses
around them, like this:
(e1&&e2)
resp.(e1||e2)
Write a parser parseExp :: Parser Exp
to accomplish this task:
data Exp = TrueE | FalseE | VarE String | OrE Exp Exp | AndE Exp Exp | NotE Exp deriving (Eq,Show) parseExp :: Parser Exp parseExp = undefined -- TODO
For example, you'd expect the following behaviour:
λ> runParser parseExp "(!x&&(y||F))" Just (AndE (NotE (VarE "x")) (OrE (VarE "y") FalseE))
For an extra challenge, you can try relaxing some of these syntactic restrictions. If you do, you have to deal with e.g:
- Relative presedence of operators: should
a||b&&c
be parsed as(a||b)&&c
ora||(b&&c)
- Associativity of operators: should
a||b||c
be parsed as(a||b)||c
ora||(b||c)
3 Maze game
Pick up the following writing prompt from the lectures: Design a game that reads in a \(n \times n\) maze from a file. The player starts at position \((0,0)\) and must reach position \((n-1,n-1)\) to win. The game accepts keyboard input to move the player around the maze.
Note that this involves deciding on a file format to represent mazes.